Evidence-based static branch prediction using machine learning
Correctly predicting the direction that branches will take is
increasingly important in today's wide-issue computer architectures.
The name program-based branch prediction is given to static
branch prediction techniques that base their prediction on a program's
structure. In this paper, we investigate a new approach to
program-based branch prediction that uses a body of existing programs
to predict the branch behavior in a new program. We call this
approach to program-based branch prediction evidence-based
static prediction, or ESP. The main idea of ESP is that the behavior
of a corpus of programs can be used to infer the behavior of new
programs. In this paper, we use neural networks and decision trees to
map static features associated with each branch to a prediction that
the branch will be taken. ESP shows significant advantages over
other prediction mechanisms. Specifically, it is a program-based
technique, it is effective across a range of programming languages and
programming styles, and it does not rely on the use of expert-defined
heuristics.
In this paper, we describe the application of ESP to the problem of
static branch prediction and compare our results to existing
program-based branch predictors. We also investigate the
applicability of ESP across computer architectures, programming
languages, compilers, and run-time systems. We provide results
showing how sensitive ESP is to the number and type of static features
and programs included in the ESP training sets, and compare
the efficacy of static branch prediction for subroutine libraries.
Averaging over a body of 43 C and Fortran programs, ESP
branch prediction results in a miss rate of 20%, as compared with the
25% miss rate obtained using the best existing program-based
heuristics.
Retrieve Paper